/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/subarray-sum-equals-k
   @Language: C++
   @Datetime: 19-04-27 17:51
   */

class Solution {
public:
	/**
	 * @param nums: a list of integer
	 * @param k: an integer
	 * @return: return an integer, denote the number of continuous subarrays whose sum equals to k
	 */
	int subarraySumEqualsK(vector<int> &nums, int k) {
		// write your code here
		unordered_multimap<int,int> prefixs={{0,0}};
		for(int i=0, sum=0; i<nums.size(); ++i){
			sum+=nums[i];
			prefixs.insert(make_pair(sum,i+1));
		}
		int count=0;
		for(auto i=prefixs.begin(); i!=prefixs.end(); ++i){
			auto range=prefixs.equal_range(i->first+k);
			for(; range.first!=range.second; ++range.first)
				if(range.first->second > i->second) ++count;
		}
		return count;
	}
};
